package sort.quicksort.leetcode;

import java.util.Random;

/**
 * @Description 215. 数组中的第K个最大元素 (TopK问题)
 * @Author Firenut
 * @Date 2023-02-12 23:35
 */
public class T215_findKthLargest {
    // TopK问题 面试一般回要求用堆排序的
    // --- 法2: 堆排序
    public int findKthLargest2(int[] nums, int k) {
        return heapSort(nums,k);
    }

    // 堆排序
    // 时间复杂度是 O(klogn) k是TopK的k,n是结点个数
    int heapSort(int[] nums,int k) {
        int len = nums.length;
        // 注:以0开始编号的完全二叉树,最后一个非叶子结点的编号为 n/2-1
        // 1.先建堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjustHeap(nums, i, len);
        }
        // 2.交换堆顶元素并重新调整堆 k*logn
        // 调整k次,即可得到第k元素的位置(不需要排完整个数组才返回,找到第k大返回即可)
        // 循环的次数: len-1-(len-k)+1 = k
        for (int i = len - 1; i >= len-k; i--) {
            // 交换堆顶元素
            swap(0, i, nums);
            // 调整堆
            adjustHeap(nums, 0, i);
        }
        return nums[nums.length-k];
    }

    // 调整堆的操作(大顶堆)
    void adjustHeap(int[] nums, int i, int len) {
        int temp = nums[i];
        for (int j = 2 * i + 1; j < len; j = j * 2 + 1) {
            if (j + 1 < len && nums[j] < nums[j + 1]) {
                j++;
            }
            if (temp > nums[j]) break;
            nums[i] = nums[j];
            i = j;
        }
        nums[i] = temp;
    }


    // ================
    // --- 法1: 快排 ---
    // 使用快排的思想,不需要进行快排
    // 使用快排的partition()每次可以得到某个元素在排序数组的正确位置
    // 所以不需要等到数组全部排序完成,再去查第k大的元素
    // 每一次都执行partition(),根据返回值判断要查找的位置在之前还是之后，然后缩小范围,递归地进行查找
    Random random = new Random(System.currentTimeMillis());
    // 排序，返回对应索引下标即可
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int left = 0;
        int right = nums.length - 1;
        while (true) {
            //经过划分,比partition大的元素都在partition右边，比partition小的元素都在partition左边
            int partiton = partition(left, right, nums);
            if (partiton == target) {
                return nums[partiton];
            } else if (partiton < target) { // 向partition的右边查找
                left = partiton + 1;
            } else { // 向partition的左边查找
                right = partiton - 1;
            }
        }
    }

    int partition(int left, int right, int[] nums) {
        int index = left + random.nextInt(right - left + 1);
        swap(left, index, nums);
        int pivot = nums[left];
        int le, gt;
        le = left + 1;
        gt = right;

        while (true) {
            while (le <= gt && nums[le] < pivot) {
                le++;
            }
            while (le <= gt && nums[gt] > pivot) {
                gt--;
            }
            if (le >= gt) {
                break;
            }
            swap(le, gt, nums);
            le++;
            gt--;
        }
        swap(gt, left, nums);
        return gt;
    }

    void swap(int i, int j, int[] nums) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
